In some wireless communication networks, procedures are provided that allow a first device to discover services provided by one or more other devices connected to the network. For example, various Layer 3 service discovery protocols may be used by devices connected to 802.11-based WiFi networks. In some systems, a first device broadcasts a request for a particular service (e.g., a printing, music, gaming, or other service), and devices on the network that hear the request (and support the requested service) send a response indicating that the service is available. Some service discovery protocols, such as those provided by Bonjour or Digital Living Network Alliance (DNLA), use lengthy string identifiers to identify services. Transmitting an entire string identifier, however, can substantially increase the overhead in service discovery request and response messages, which may be particularly undesirable for low-power devices. Conversely, the use of shorter service identifiers (e.g., by using a hash of a string identifier) can lead to ambiguity. In particular, shorter identifiers increase the probability of a “collision” in which two or more services are represented by the same identifying information.